package com.zang.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZVerify
 * @since 2022/10/30 19:34
 **/
public class 相同的树 {

    Deque<TreeNode> list = new LinkedList<>();
    boolean flag = true;
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if (p==null && q==null) return true;

        dfs(p,q);
        if (!flag) return false;
        return list.isEmpty();
    }

    private void dfs(TreeNode p, TreeNode q) {
        if (p==null && q == null) {
            return;
        }
        if (p==null || q==null) {
            flag = false;
            return;
        }
        list.addLast(p);
        list.addLast(q);
        if (p.val==q.val) {list.pop();list.pop();}
        dfs(p.left,q.left);
        dfs(p.right,q.right);
    }
}
